#include <vector>
#include <stdexcept>

using namespace std;

class Heap
{
private:
    vector<int> maxHeap;

public:
    /* 构造方法，根据输入列表建堆 */
    Heap(vector<int> nums)
    {
        maxHeap = nums;
        for (int i = parent(size() - 1); i >= 0; i--)
        {
            siftDown(i);
        }
    };

    ~Heap(){};

    /* 元素入堆 */
    void push(int val)
    {
        maxHeap.push_back(val);
        siftUp(size() - 1);
    }

    /* 从节点 i 开始，从底至顶堆化 */
    void siftUp(int i)
    {
        while (true)
        {
            int p = parent(i);
            if (p < 0 || maxHeap[i] <= maxHeap[p])
                break;
            swap(maxHeap[i], maxHeap[p]);
            i = p;
        }
    }

    /* 元素出堆 */
    void pop()
    {
        if (empty())
        {
            throw out_of_range("堆为空");
        }
        swap(maxHeap[0], maxHeap[size() - 1]);
        maxHeap.pop_back();
        siftDown(0);
    }

    /* 从节点 i 开始，从顶至底堆化 */
    void siftDown(int i)
    {
        while (true)
        {
            int l = left(i), r = right(i), ma = i;
            if (l < size() && maxHeap[l] > maxHeap[ma])
                ma = l;
            if (r < size() && maxHeap[r] > maxHeap[ma])
                ma = r;
            if (ma == i)
                break;
            swap(maxHeap[i], maxHeap[ma]);
            i = ma;
        }
    }

    /* 获取左子节点索引 */
    int left(int i)
    {
        return 2 * i + 1;
    }

    /* 获取右子节点索引 */
    int right(int i)
    {
        return 2 * i + 2;
    }

    /* 获取父节点索引 */
    int parent(int i)
    {
        return (i - 1) / 2;
    }

    /* 访问堆顶元素 */
    int peek()
    {
        return maxHeap[0];
    }

    int size()
    {
        return maxHeap.size();
    }

    bool empty()
    {
        return maxHeap.empty();
    }
};
